package zuoshen_mid.class1.skill2_tableGreedy;


import org.junit.Test;

/* 
    通过两个类型的袋子购买苹果：6个一袋或者8个一袋
    要求最后总数为n
    且必须让 **每个袋子都装满**， 如果无论如何都不能做到，返回-1
    否则返回最小的袋子数
*/
public class BuyApplesByBags {
    public int buyApples(int n) {
        if (n == 0) return -1;
        int res = dfs(n, 0);
        if (res == Integer.MAX_VALUE) return -1;
        else return res;
    }

    public int dfs(int n, int cur) {
        if (n == 0) return cur;
        if (n % 2 == 1 || n < 6) return Integer.MAX_VALUE;
        return Math.min(dfs(n - 6, cur + 1), dfs(n - 8, cur + 1));
    }

    public int buyApples2(int n) {
        int[] f = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            if (i < 6 || i % 2 == 1) {
                f[i] = -1;
            } else if (i == 6 || i == 8) {
                f[i] = 1;
            } else {
                if (f[i - 6] < 0 && f[i - 8] < 0) {
                    f[i] = -1;
                } else {
                    if (f[i - 6] > 0 && f[i - 8] > 0) {
                        f[i] = Math.min(f[i - 6], f[i - 8]) + 1; 
                    }else if (f[i - 8] > 0) {
                        f[i] = f[i - 8] + 1;
                    } else {
                        f[i] = f[i - 6] + 1;
                    }
                }
            }
        }
        return f[n];
    }

    public int buyApples3(int n) {
        //找到8的最大袋子数，直到24以下
        int bag8 = n / 8;
        int rest = n % 8;
        //为什么小于24？ 若大于24，用8和6都能搞定24，剩下的部分即rest-24再由袋子搞定
        //既然如此，那我在24以下肯定找不到解了
        while (bag8 >= 0 && rest < 24) {
            if (rest % 6 == 0) {
                return bag8 + rest / 6;
            } else {
                rest += 8;
                bag8--;
            }
        }
        return -1;
    }

    public int buyApples4(int n) {
        if (n % 2 == 1) return -1;
        if (n < 18) {
            switch(n) {
                case 6: return 1;
                case 8: return 1;
                case 12: return 2;
                case 14: return 2;
                case 16: return 2;
                default: return -1;
            }
        }

        return (n - 18) / 8 + 3;
    }

    @Test
    public void test() {
        for (int i = 0; i < 100; i++) {
            /* if (buyApples(i) != buyApples2(i) || buyApples2(i) != buyApples3(i)) {
                System.out.println(i);
            } */
            System.out.print(i + ": " + buyApples4(i) + "\t" /* + " " + buyApples4(i) */);
            if ((i + 1 - 18) % 8 == 0) System.out.println();
        }
    }
}
